import java.util.*;

public class 复原IP地址 {
    public StringBuilder path;
    public List<String> ans;
    public int n;
    public List<String> restoreIpAddresses (String s) {
        ans = new ArrayList<>();
        path = new StringBuilder();
        n = s.length();
        if (n < 4) {
            return ans;
        }
        dfs(0,0,s);
        return ans;
    }

    public void dfs (int pos,int point,String s) {
        if (point == 4) {
            if (pos == s.length()) {
                path.deleteCharAt(path.length() - 1);
                ans.add(path.toString());
            }
            return;
        }
        for (int i = pos;i < n && i < pos + 3;i++) {
            char ch = s.charAt(pos);
            // 无效字符
            if (ch < '0' || ch > '9') {
                return;
            }
            // 转成整数
            int n = Integer.parseInt(s.substring(pos,i + 1));
            // 判断是否存在前导零
            if (i > pos && s.charAt(pos) == '0') {
                return;
            }
            // 不能超过 255
            if (n > 255) {
                return;
            }
            // 添加入 path 中
            int len = path.length();
            path.append(s.substring(pos,i + 1) + ".");
            dfs(i + 1,point + 1,s);
            path.setLength(len);
        }
    }
}
